package Leetcode第二期;

/**
 * @author : K k
 * @date : 15:12 2020/9/18
 */
public class 我能赢吗_464 {
    boolean[] visited;

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        visited=new boolean[maxChoosableInteger+1];
        int sum=(1+maxChoosableInteger)*maxChoosableInteger/2;
        Boolean[] dp=new Boolean[maxChoosableInteger+1];
        return dfsSovler(maxChoosableInteger, desiredTotal,dp,1);
    }

    /**
     * @param maxChoosableInteger 可选数组
     * @param desiredTotal  总数
     * @param dp  结果数组
     * @param i 当前数字
     * @return
     */
    private boolean dfsSovler(int maxChoosableInteger, int desiredTotal, Boolean[] dp, int i) {
        if (dp[i]!=null){
            return dp[i];
        }


        for (int j=1;j<=maxChoosableInteger;j++) {
            if (visited[j] == true) {
                continue;
            }
            visited[j] = true;
            //搜索找到一个可以稳赢的开头
            if (desiredTotal - j <= 0 || dfsSovler(maxChoosableInteger, desiredTotal - j, dp, j)==false) {
                return dp[i] = true;
            }
            visited[j] = false;
        }
        //不能稳赢
        return dp[i];
    }

    public static void main(String[] args) {
        我能赢吗_464 x= new 我能赢吗_464();
        System.out.println(x.canIWin(10, 11));
    }
}
